//===-- OptimizerStatsUtils.cpp - Utils for collecting stats  -*- C++ ---*-===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
///
/// \file
///
/// This file implements collection and dumping of statistics about PILModules,
/// PILFunctions and memory consumption during the execution of PIL
/// optimization pipelines.
///
/// The following statistics are collected:
/// - For PILFunctions: the number of PIL basic blocks, the number of PIL
/// instructions
///
/// - For PILModules: the number of PIL basic blocks, the number of PIL
/// instructions, the number of PILFunctions, the amount of memory used by the
/// compiler.
///
/// By default, any collection of statistics is disabled to avoid affecting
/// compile times.
///
/// One can enable the collection of statistics and dumping of these statistics
/// for the whole PILModule and/or for PILFunctions.
///
/// To reduce the amount of produced data, one can set thresholds in such a way
/// that changes in the statistics are only reported if the delta between the
/// old and the new values are at least X%. The deltas are computed using the
/// following formula:
///  Delta = (NewValue - OldValue) / OldValue
///
/// Thresholds provide a simple way to perform a simple filtering of the
/// collected statistics during the compilation. But if there is a need for a
/// more complex analysis of collected data (e.g. aggregation by a pipeline
/// stage or by the type of a transformation), it is often better to dump
/// as much data as possible into a file using e.g. `-sil-stats-dump-all
/// -sil-stats-modules -sil-stats-functions` and then e.g. use the helper scripts
/// to store the collected data into a database and then perform complex queries
/// on it. Many kinds of analysis can be then formulated pretty easily as SQL
/// queries.
///
/// The output format is a set of CSV (comma separated values) lines. Each lines
/// represents one counter or one counter change.
///
/// For counter updates it looks like this:
///  Kind, CounterName, StageName, TransformName, TransformPassNumber,
///  DeltaValue, OldCounterValue, NewCounterValue, Duration, Symbol
///
/// For counter updates it looks like this:
///  Kind, CounterName, StageName, TransformName, TransformPassNumber,
///  CounterValue, Duration, Symbol
///
/// where Kind is one of "function", "module", "function_history",
///       CounterName is one of "block", "inst", "function", "memory",
///       Symbol is e.g. the name of a function.
///       StageName and TransformName are the names of the current optimizer
///       pipeline stage and current transform.
///       Duration is the duration of the transformation.
//===----------------------------------------------------------------------===//

#include "polarphp/pil/lang/PILValue.h"
#include "polarphp/pil/lang/PILVisitor.h"
#include "polarphp/pil/optimizer/analysis/Analysis.h"
#include "polarphp/pil/optimizer/passmgr/PassManager.h"
#include "polarphp/pil/optimizer/passmgr/Transforms.h"
#include "polarphp/pil/optimizer/utils/OptimizerStatsUtils.h"

#include "llvm/Support/CommandLine.h"
#include "llvm/Support/FileSystem.h"
#include "llvm/Support/Process.h"

using namespace polar;

namespace {

/// The total number of different kinds of PILInstructions.
constexpr unsigned NumPILInstructions =
   unsigned(PILNodeKind::Last_PILInstruction)
   - unsigned(PILNodeKind::First_PILInstruction)
   + 1;

static unsigned getIndexForKind(PILInstructionKind kind) {
   return unsigned(kind) - unsigned(PILNodeKind::First_PILInstruction);
}

/// A set of counters, one per PILInstruction kind.
class InstructionCounts {
   unsigned Counts[NumPILInstructions] = {};

public:
   constexpr InstructionCounts() {}

   unsigned &operator[](PILInstructionKind kind) {
      return Counts[getIndexForKind(kind)];
   }

   void addAll(const InstructionCounts &other) {
      for (unsigned i = 0; i != NumPILInstructions; ++i) {
         Counts[i] += other.Counts[i];
      }
   }

   void subAll(const InstructionCounts &other) {
      for (unsigned i = 0; i != NumPILInstructions; ++i) {
         Counts[i] -= other.Counts[i];
      }
   }
};

/// A helper type to parse a comma separated list of PIL instruction names
/// provided as argument of the -sil-stats-only-instructions options.
class StatsOnlyInstructionsOpt {
   bool ShouldComputeInstCounts[NumPILInstructions] = {};

   /// The number of different kinds of PILInstructions to be tracked.
   unsigned NumInstCounts = 0;

public:
   constexpr StatsOnlyInstructionsOpt() {}

   void operator=(StringRef val) {
      if (val.empty())
         return;
      if (val == "all") {
         for (auto &inst : ShouldComputeInstCounts) {
            inst = true;
         }
         NumInstCounts = NumPILInstructions;
         return;
      }
      SmallVector<StringRef, 8> statsInstNames;
      val.split(statsInstNames, ',', -1, false);
      for (auto instName : statsInstNames) {
         // Check if it is a known instruction.
         auto kind = getPILInstructionKind(instName);
         unsigned index = getIndexForKind(kind);
         if (!ShouldComputeInstCounts[index]) {
            ShouldComputeInstCounts[index] = true;
            NumInstCounts++;
         }
      }
   }

   bool shouldComputeInstCount(PILInstructionKind kind) const {
      return ShouldComputeInstCounts[getIndexForKind(kind)];
   }

   int getInstCountsNum() const {
      return NumInstCounts;
   }
};

StatsOnlyInstructionsOpt StatsOnlyInstructionsOptLoc;

/// Use this option like -Xllvm -sil-stats-only-instructions=strong_retain,alloc_stack
/// If you need to track all kinds of PILInstructions, you can use
/// -sil-stats-only-instructions=all
llvm::cl::opt<StatsOnlyInstructionsOpt, true, llvm::cl::parser<std::string>>
   StatsOnlyInstructions(
   "sil-stats-only-instructions",
   llvm::cl::desc(
      "Comma separated list of PIL insruction names, whose stats "
      "should be collected"),
   llvm::cl::Hidden, llvm::cl::ZeroOrMore,
   llvm::cl::value_desc("instruction name"),
   llvm::cl::location(StatsOnlyInstructionsOptLoc),
   llvm::cl::ValueRequired);

/// Dump as much statistics as possible, ignore any thresholds.
llvm::cl::opt<bool> PILStatsDumpAll(
   "sil-stats-dump-all", llvm::cl::init(false),
   llvm::cl::desc("Dump all PIL module and PIL function stats"));

/// Dump statistics about the PILModule.
llvm::cl::opt<bool> PILStatsModules(
   "sil-stats-modules", llvm::cl::init(false),
   llvm::cl::desc("Enable computation of statistics for PIL modules"));

/// Dump statistics about PILFunctions.
llvm::cl::opt<bool> PILStatsFunctions(
   "sil-stats-functions", llvm::cl::init(false),
   llvm::cl::desc("Enable computation of statistics for PIL functions"));

/// The name of the output file for optimizer counters.
llvm::cl::opt<std::string> PILStatsOutputFile(
   "sil-stats-output-file", llvm::cl::init(""),
   llvm::cl::desc("The name of the output file for optimizer counters"));

/// A threshold in percents for the PIL basic block counters.
llvm::cl::opt<double> BlockCountDeltaThreshold(
   "sil-stats-block-count-delta-threshold", llvm::cl::init(1),
   llvm::cl::desc(
      "Threshold for reporting changed basic block count numbers"));

/// A threshold in percents for the PIL instructions counters.
llvm::cl::opt<double> InstCountDeltaThreshold(
   "sil-stats-inst-count-delta-threshold", llvm::cl::init(1),
   llvm::cl::desc(
      "Threshold for reporting changed instruction count numbers"));

/// A threshold in percents for the PIL functions counters.
llvm::cl::opt<double> FunctionCountDeltaThreshold(
   "sil-stats-function-count-delta-threshold", llvm::cl::init(1),
   llvm::cl::desc("Threshold for reporting changed function count numbers"));

/// A threshold in percents for the counters of memory used by the compiler.
llvm::cl::opt<double> UsedMemoryDeltaThreshold(
   "sil-stats-used-memory-delta-threshold", llvm::cl::init(5),
   llvm::cl::desc("Threshold for reporting changed memory usage numbers"));

llvm::cl::opt<double> UsedMemoryMinDeltaThreshold(
   "sil-stats-used-memory-min-threshold", llvm::cl::init(1),
   llvm::cl::desc("Min hreshold for reporting changed memory usage numbers"));

/// A threshold in percents for the basic blocks counter inside a PILFunction.
/// Has effect only if it is used together with -sil-stats-functions.
llvm::cl::opt<double> FuncBlockCountDeltaThreshold(
   "sil-stats-func-block-count-delta-threshold", llvm::cl::init(200),
   llvm::cl::desc("Threshold for reporting changed basic block count numbers "
                  "for a function"));

/// A minimal threshold (in number of basic blocks) for the basic blocks counter
/// inside a PILFunction. Only functions with more basic blocks than this
/// threshold are reported. Has effect only if it is used together with
/// -sil-stats-functions.
llvm::cl::opt<int> FuncBlockCountMinThreshold(
   "sil-stats-func-block-count-min-threshold", llvm::cl::init(50),
   llvm::cl::desc(
      "Min threshold for reporting changed basic block count numbers "
      "for a function"));

/// A threshold in percents for the PIL instructions counter inside a
/// PILFunction. Has effect only if it is used together with
/// -sil-stats-functions.
llvm::cl::opt<double> FuncInstCountDeltaThreshold(
   "sil-stats-func-inst-count-delta-threshold", llvm::cl::init(200),
   llvm::cl::desc("Threshold for reporting changed instruction count numbers "
                  "for a function"));

/// A minimal threshold (in number of instructions) for the PIL instructions
/// counter inside a PILFunction. Only functions with more instructions than
/// this threshold are reported. Has effect only if it is used together with
/// -sil-stats-functions.
llvm::cl::opt<int> FuncInstCountMinThreshold(
   "sil-stats-func-inst-count-min-threshold", llvm::cl::init(300),
   llvm::cl::desc(
      "Min threshold for reporting changed instruction count numbers "
      "for a function"));

/// Track only statistics for a function with a given name.
/// Has effect only if it is used together with -sil-stats-functions.
llvm::cl::opt<std::string> StatsOnlyFunctionName(
   "sil-stats-only-function", llvm::cl::init(""),
   llvm::cl::desc("Function name, whose stats should be tracked"));

/// Track only statistics for a function whose name contains a given substring.
/// Has effect only if it is used together with -sil-stats-functions.
llvm::cl::opt<std::string> StatsOnlyFunctionsNamePattern(
   "sil-stats-only-functions", llvm::cl::init(""),
   llvm::cl::desc(
      "Pattern of a function name, whose stats should be tracked"));

/// Stats for a PIL function.
struct FunctionStat {
   int BlockCount = 0;
   int InstCount = 0;
   /// Instruction counts per PILInstruction kind.
   InstructionCounts InstCounts;

   FunctionStat(PILFunction *F);
   FunctionStat() {}

   void print(llvm::raw_ostream &stream) const {
      stream << "FunctionStat("
             << "blocks = " << BlockCount << ", Inst = " << InstCount << ")\n";
   }

   bool operator==(const FunctionStat &rhs) const {
      return BlockCount == rhs.BlockCount && InstCount == rhs.InstCount;
   }

   bool operator!=(const FunctionStat &rhs) const { return !(*this == rhs); }

   void dump() { print(llvm::errs()); }
};

/// Stats a single PIL module.
struct ModuleStat {
   /// Total number of PILFunctions in the current PILModule.
   int FunctionCount = 0;
   /// Total number of PILBasicBlocks in the current PILModule.
   int BlockCount = 0;
   /// Total number of PILInstructions in the current PILModule.
   int InstCount = 0;
   /// Total amount of memory used by the compiler.
   int UsedMemory = 0;
   /// Total number of PILInstructions created since the beginning of the current
   /// compilation.
   int CreatedInstCount = 0;
   /// Total number of PILInstructions deleted since the beginning of the current
   /// compilation.
   int DeletedInstCount = 0;
   /// Instruction counts per PILInstruction kind.
   InstructionCounts InstCounts;

   ModuleStat() {}

   /// Add the stats for a given function to the total module stats.
   void addFunctionStat(FunctionStat &Stat) {
      BlockCount += Stat.BlockCount;
      InstCount += Stat.InstCount;
      ++FunctionCount;
      if (!StatsOnlyInstructionsOptLoc.getInstCountsNum())
         return;
      InstCounts.addAll(Stat.InstCounts);
   }

   /// Subtract the stats for a given function from total module stats.
   void subFunctionStat(FunctionStat &Stat) {
      BlockCount -= Stat.BlockCount;
      InstCount -= Stat.InstCount;
      --FunctionCount;
      if (!StatsOnlyInstructionsOptLoc.getInstCountsNum())
         return;
      InstCounts.subAll(Stat.InstCounts);
   }

   /// Add the stats about current memory usage.
   void addMemoryStat() {
      UsedMemory = llvm::sys::Process::GetMallocUsage();
   }

   /// Add the stats about created and deleted instructions.
   void addCreatedAndDeletedInstructionsStat() {
      CreatedInstCount = PILInstruction::getNumCreatedInstructions();
      DeletedInstCount = PILInstruction::getNumDeletedInstructions();
   }

   void print(llvm::raw_ostream &stream) const {
      stream << "ModuleStat(functions = " << FunctionCount
             << ", blocks = " << BlockCount << ", Inst = " << InstCount
             << ", UsedMemory = " << UsedMemory / (1024 * 1024)
             << ", CreatedInst = " << CreatedInstCount
             << ", DeletedInst = " << DeletedInstCount
             << ")\n";
   }

   void dump() { print(llvm::errs()); }

   bool operator==(const ModuleStat &rhs) const {
      return FunctionCount == rhs.FunctionCount && BlockCount == rhs.BlockCount &&
             InstCount == rhs.InstCount && UsedMemory == rhs.UsedMemory;
   }

   bool operator!=(const ModuleStat &rhs) const { return !(*this == rhs); }
};

// A helper type to collect the stats about the number of instructions and basic
// blocks.
struct InstCountVisitor : PILInstructionVisitor<InstCountVisitor> {
   int BlockCount = 0;
   int InstCount = 0;
   InstructionCounts &InstCounts;

   InstCountVisitor(InstructionCounts &InstCounts) : InstCounts(InstCounts) {}

   int getBlockCount() const {
      return BlockCount;
   }

   int getInstCount() const {
      return InstCount;
   }

   void visitPILBasicBlock(PILBasicBlock *BB) {
      ++BlockCount;
      PILInstructionVisitor<InstCountVisitor>::visitPILBasicBlock(BB);
   }

   void visit(PILInstruction *I) {
      ++InstCount;
      ++InstCounts[I->getKind()];
   }
};

/// A helper type to store different parameters related to the current transform.
class TransformationContext {
   /// PILModule being processed.
   PILModule &M;
   /// The pass manager being used.
   PILPassManager &PM;
   /// The transformation that was/will be performed.
   PILTransform *Transform;
   /// The time it took to perform the transformation.
   int Duration;
   /// The pass number in the optimizer pipeline.
   int PassNumber;

public:
   TransformationContext(PILModule &M, PILPassManager &PM,
                         PILTransform *Transform, int PassNumber, int Duration)
      : M(M), PM(PM), Transform(Transform), Duration(Duration),
        PassNumber(PassNumber) {}

   int getPassNumber() const {
      return PassNumber;
   }

   int getDuration() const {
      return Duration;
   }

   StringRef getTransformId() const {
      return Transform->getID();
   }

   StringRef getStageName() const {
      return PM.getStageName();
   }

   PILModule &getModule() {
      return M;
   }

   PILPassManager &getPassManager() {
      return PM;
   }
};

/// Aggregated statistics for the whole PILModule and all PILFunctions belonging
/// to it.
class AccumulatedOptimizerStats {
   using FunctionStats = llvm::DenseMap<const PILFunction *, FunctionStat>;

   /// Current stats for each function.
   FunctionStats FuncStats;
   /// Current stats for the module.
   ModuleStat ModStat;

public:
   FunctionStat &getFunctionStat(const PILFunction *F) {
      return FuncStats[F];
   }

   ModuleStat &getModuleStat() {
      return ModStat;
   }

   void deleteFunctionStat(PILFunction *F) {
      FuncStats.erase(F);
   }
};

/// A helper class to repesent the module stats as an analysis,
/// so that it is preserved across multiple passes.
class OptimizerStatsAnalysis : public PILAnalysis {
   PILModule &M;
   /// The actual cache holding all the statistics.
   std::unique_ptr<AccumulatedOptimizerStats> Cache;

   /// Sets of functions changed, deleted or added since the last
   /// computation of statistics. These sets are used to avoid complete
   /// re-computation of the stats for the whole module. Instead only
   /// re-compute the stats for the changed functions, which is much
   /// faster.
   SmallVector<PILFunction *, 16> InvalidatedFuncs;
   SmallVector<PILFunction *, 16> DeletedFuncs;
   SmallVector<PILFunction *, 16> AddedFuncs;

public:
   OptimizerStatsAnalysis(PILModule *M)
      : PILAnalysis(PILAnalysisKind::OptimizerStats), M(*M), Cache(nullptr) {}

   static bool classof(const PILAnalysis *S) {
      return S->getKind() == PILAnalysisKind::OptimizerStats;
   }

   /// Invalidate all information in this analysis.
   virtual void invalidate() override {
      // This analysis is never invalidated, because it just used
      // to store the statistics.
   }

   /// Invalidate all of the information for a specific function.
   virtual void invalidate(PILFunction *F, InvalidationKind K) override {
      InvalidatedFuncs.push_back(F);
   }

   /// Notify the analysis about a newly created function.
   virtual void notifyAddedOrModifiedFunction(PILFunction *F) override {
      AddedFuncs.push_back(F);
   }

   /// Notify the analysis about a function which will be deleted from the
   /// module.
   virtual void notifyWillDeleteFunction(PILFunction *F) override {
      DeletedFuncs.push_back(F);
   };

   /// Notify the analysis about changed witness or vtables.
   virtual void invalidateFunctionTables() override {
   }


   PILModule &getModule() const {
      return M;
   }

   /// Get the collected statistics for a function.
   FunctionStat &getFunctionStat(const PILFunction *F) {
      if (!Cache)
         Cache = std::make_unique<AccumulatedOptimizerStats>();

      return Cache->getFunctionStat(F);
   }

   /// Get the collected statistics for a module.
   ModuleStat &getModuleStat() {
      if (!Cache)
         Cache = std::make_unique<AccumulatedOptimizerStats>();

      return Cache->getModuleStat();
   }

   /// Update module stats after running the Transform.
   void updateModuleStats(TransformationContext &Ctx);
};

class NewLineInserter {
   bool isNewline = true;

public:
   NewLineInserter() {}
   StringRef get() {
      StringRef result =  isNewline ? "\n" : "";
      isNewline = false;
      return result;
   }
};

/// The output stream to be used for writing the collected statistics.
/// Use the unique_ptr to ensure that the file is properly closed upon
/// exit.
std::unique_ptr<llvm::raw_ostream, void(*)(llvm::raw_ostream *)>
   stats_output_stream = {nullptr, nullptr};

/// Return the output streamm to be used for logging the collected statistics.
llvm::raw_ostream &stats_os() {
   // Initialize the stream if it is not initialized yet.
   if (!stats_output_stream) {
      // If there is user-defined output file name, use it.
      if (!PILStatsOutputFile.empty()) {
         // Try to open the file.
         std::error_code EC;
         auto fd_stream = std::make_unique<llvm::raw_fd_ostream>(
            PILStatsOutputFile, EC, llvm::sys::fs::OpenFlags::F_Text);
         if (!fd_stream->has_error() && !EC) {
            stats_output_stream = {fd_stream.release(),
                                   [](llvm::raw_ostream *d) { delete d; }};
            return *stats_output_stream.get();
         }
         fd_stream->clear_error();
         llvm::errs() << PILStatsOutputFile << " : " << EC.message() << "\n";
      }
      // Otherwise use llvm::errs() as output. No need to destroy it at the end.
      stats_output_stream = {&llvm::errs(), [](llvm::raw_ostream *d) {}};
   }
   return *stats_output_stream.get();
}

/// A helper function to dump the counter value.
void printCounterValue(StringRef Kind, StringRef CounterName, int CounterValue,
                       StringRef Symbol, TransformationContext &Ctx) {
   stats_os() << Kind;
   stats_os() << ", ";

   stats_os() << CounterName;
   stats_os() << ", ";

   stats_os() << Ctx.getStageName();
   stats_os() << ", ";

   stats_os() << Ctx.getTransformId();
   stats_os() << ", ";

   stats_os() << Ctx.getPassNumber();
   stats_os() << ", ";

   stats_os() << CounterValue;
   stats_os() << ", ";

   stats_os() << Ctx.getDuration();
   stats_os() << ", ";

   stats_os() << Symbol;
   stats_os() << "\n";
}

/// A helper function to dump the change of the counter value.
void printCounterChange(StringRef Kind, StringRef CounterName, double Delta,
                        int OldValue, int NewValue, TransformationContext &Ctx,
                        StringRef Symbol = "") {
   stats_os() << Kind;
   stats_os() << ", ";

   stats_os() << CounterName;
   stats_os() << ", ";

   stats_os() << Ctx.getStageName();
   stats_os() << ", ";

   stats_os() << Ctx.getTransformId();
   stats_os() << ", ";

   stats_os() << Ctx.getPassNumber();
   stats_os() << ", ";

   llvm::format_provider<double>::format(Delta, stats_os(), "f8");
   stats_os() << ", ";

   stats_os() << OldValue;
   stats_os() << ", ";

   stats_os() << NewValue;
   stats_os() << ", ";

   stats_os() << Ctx.getDuration();
   stats_os() << ", ";

   stats_os() << Symbol;
   stats_os() << "\n";
}

/// Check if a function name matches the pattern provided by the user.
bool isMatchingFunction(PILFunction *F, bool shouldHaveNamePattern = false) {
   auto FuncName = F->getName();
   // Is it an exact string match?
   if (!StatsOnlyFunctionName.empty())
      return F->getName() == StatsOnlyFunctionName;

   // Does the name contain a user-defined substring?
   if (!StatsOnlyFunctionsNamePattern.empty()) {
      return FuncName.contains(StatsOnlyFunctionsNamePattern);
   }

   return shouldHaveNamePattern ? true : false;
}

/// Compute the delta between the old and new values.
/// Return it as a percent value.
double computeDelta(int Old, int New) {
   return 100.0 * (Old ? ((New - Old) * 1.0 / Old) : 0.0);
}

/// Returns true if it is a first time we collect data for a given counter.
/// This is the case if the old value is 0 and the new one is something
/// different, i.e. we didn't have any statistics about it.
bool isFirstTimeData(int Old, int New) {
   return Old == 0 && New != Old;
}

/// Dump statistics for a PILFunction. It is only used if a user asked to
/// produce detailed stats about transformations of PILFunctions. This
/// information is dumped unconditionally, for each transformation that changed
/// the function in any form. No thresholds are taken into account.
///
/// \param Stat statistics computed now, after the run of the transformation
/// \param Ctx transformation context to be used
void processFuncStatHistory(PILFunction *F, FunctionStat &Stat,
                            TransformationContext &Ctx) {
   if (!PILStatsFunctions)
      return;

   if (!PILStatsDumpAll && !isMatchingFunction(F, /*shouldHaveNamePattern*/ true))
      return;

   printCounterValue("function_history", "block", Stat.BlockCount, F->getName(),
                     Ctx);
   printCounterValue("function_history", "inst", Stat.InstCount, F->getName(),
                     Ctx);

   /// Dump collected instruction counts.
   if (!StatsOnlyInstructionsOptLoc.getInstCountsNum())
      return;

   for (auto kind : allPILInstructionKinds()) {
      if (!Stat.InstCounts[kind])
         continue;
      if (!StatsOnlyInstructionsOptLoc.shouldComputeInstCount(kind))
         continue;
      std::string CounterName = "inst_";
      CounterName += getPILInstructionName(kind);
      printCounterValue("function_history", CounterName, Stat.InstCounts[kind],
                        F->getName(), Ctx);
   }
}

/// Process PILFunction's statistics changes.
///
/// \param OldStat statistics computed last time
/// \param NewStat statistics computed now, after the run of the transformation
/// \param Ctx transformation context to be used
void processFuncStatsChanges(PILFunction *F, FunctionStat &OldStat,
                             FunctionStat &NewStat,
                             TransformationContext &Ctx) {
   processFuncStatHistory(F, NewStat, Ctx);

   if (!PILStatsFunctions && !PILStatsDumpAll)
      return;

   if (OldStat == NewStat)
      return;

   if ((!StatsOnlyFunctionsNamePattern.empty() ||
        !StatsOnlyFunctionName.empty()) &&
       !isMatchingFunction(F))
      return;

   // Compute deltas.
   double DeltaBlockCount = computeDelta(OldStat.BlockCount, NewStat.BlockCount);
   double DeltaInstCount = computeDelta(OldStat.InstCount, NewStat.InstCount);

   NewLineInserter nl;

   // TODO: handle cases where a function got smaller.
   if ((PILStatsDumpAll &&
        (DeltaBlockCount != 0.0 || OldStat.BlockCount == 0)) ||
       (std::abs(DeltaBlockCount) > FuncBlockCountDeltaThreshold &&
        OldStat.BlockCount > FuncBlockCountMinThreshold)) {
      stats_os() << nl.get();
      printCounterChange("function", "block", DeltaBlockCount, OldStat.BlockCount,
                         NewStat.BlockCount, Ctx, F->getName());
   }

   if ((PILStatsDumpAll && (DeltaInstCount != 0.0 || OldStat.InstCount == 0)) ||
       (std::abs(DeltaInstCount) > FuncInstCountDeltaThreshold &&
        OldStat.InstCount > FuncInstCountMinThreshold)) {
      stats_os() << nl.get();
      printCounterChange("function", "inst", DeltaInstCount, OldStat.InstCount,
                         NewStat.InstCount, Ctx, F->getName());
   }
}

/// Process PILModule's statistics changes.
///
/// \param OldStat statistics computed last time
/// \param NewStat statistics computed now, after the run of the transformation
/// \param Ctx transformation context to be used
void processModuleStatsChanges(ModuleStat &OldStat, ModuleStat &NewStat,
                               TransformationContext &Ctx) {
   if (!PILStatsModules && !PILStatsDumpAll)
      return;

   // Bail if no changes.
   if (OldStat == NewStat)
      return;

   // Compute deltas.
   double DeltaBlockCount = computeDelta(OldStat.BlockCount, NewStat.BlockCount);
   double DeltaInstCount = computeDelta(OldStat.InstCount, NewStat.InstCount);
   double DeltaFunctionCount =
      computeDelta(OldStat.FunctionCount, NewStat.FunctionCount);
   double DeltaUsedMemory = computeDelta(OldStat.UsedMemory, NewStat.UsedMemory);

   NewLineInserter nl;

   // Print delta for blocks only if it is above a threshold or we are asked to
   // dump all changes.
   if ((PILStatsDumpAll &&
        (DeltaBlockCount != 0.0 ||
         isFirstTimeData(OldStat.BlockCount, NewStat.BlockCount))) ||
       (std::abs(DeltaBlockCount) > BlockCountDeltaThreshold)) {
      stats_os() << nl.get();
      printCounterChange("module", "block", DeltaBlockCount, OldStat.BlockCount,
                         NewStat.BlockCount, Ctx);
   }

   // Print delta for instructions only if it is above a threshold or we are
   // asked to dump all changes.
   if ((PILStatsDumpAll &&
        (DeltaInstCount != 0.0 ||
         isFirstTimeData(OldStat.InstCount, NewStat.InstCount))) ||
       (std::abs(DeltaInstCount) > InstCountDeltaThreshold)) {
      stats_os() << nl.get();
      printCounterChange("module", "inst", DeltaInstCount, OldStat.InstCount,
                         NewStat.InstCount, Ctx);
   }

   // Print delta for functions only if it is above a threshold or we are
   // asked to dump all changes.
   if ((PILStatsDumpAll &&
        (DeltaFunctionCount != 0.0 ||
         isFirstTimeData(OldStat.FunctionCount, NewStat.FunctionCount))) ||
       (std::abs(DeltaFunctionCount) > FunctionCountDeltaThreshold)) {
      stats_os() << nl.get();
      printCounterChange("module", "functions", DeltaFunctionCount,
                         OldStat.FunctionCount, NewStat.FunctionCount, Ctx);
   }

   // Print delta for the used memory only if it is above a threshold or we are
   // asked to dump all changes.
   if ((PILStatsDumpAll &&
        (std::abs(DeltaUsedMemory) > UsedMemoryMinDeltaThreshold ||
         isFirstTimeData(OldStat.UsedMemory, NewStat.UsedMemory))) ||
       (std::abs(DeltaUsedMemory) > UsedMemoryDeltaThreshold)) {
      stats_os() << nl.get();
      printCounterChange("module", "memory", DeltaUsedMemory, OldStat.UsedMemory,
                         NewStat.UsedMemory, Ctx);
   }


   if (PILStatsDumpAll) {
      // Dump stats about the number of created and deleted instructions.
      auto DeltaCreatedInstCount =
         computeDelta(OldStat.CreatedInstCount, NewStat.CreatedInstCount);
      auto DeltaDeletedInstCount =
         computeDelta(OldStat.DeletedInstCount, NewStat.DeletedInstCount);
      if (DeltaCreatedInstCount != 0.0 ||
          isFirstTimeData(OldStat.CreatedInstCount, NewStat.CreatedInstCount))
         printCounterChange("module", "created_inst", DeltaCreatedInstCount,
                            OldStat.CreatedInstCount, NewStat.CreatedInstCount,
                            Ctx);
      if (DeltaDeletedInstCount != 0.0 ||
          isFirstTimeData(OldStat.DeletedInstCount, NewStat.DeletedInstCount))
         printCounterChange("module", "deleted_inst", DeltaDeletedInstCount,
                            OldStat.DeletedInstCount, NewStat.DeletedInstCount,
                            Ctx);
   }

   /// Dump collected instruction counts.
   if (!StatsOnlyInstructionsOptLoc.getInstCountsNum())
      return;

   for (auto kind : allPILInstructionKinds()) {
      // Do not print anything, if there is no change.
      if (OldStat.InstCounts[kind] == NewStat.InstCounts[kind])
         continue;
      if (!StatsOnlyInstructionsOptLoc.shouldComputeInstCount(kind))
         continue;
      SmallString<64> CounterName("inst_");
      CounterName += getPILInstructionName(kind);
      auto DeltaCounterKindCount =
         computeDelta(OldStat.InstCounts[kind], NewStat.InstCounts[kind]);
      printCounterChange("module", CounterName, DeltaCounterKindCount,
                         OldStat.InstCounts[kind], NewStat.InstCounts[kind], Ctx);
   }
}

/// Update the stats for a module after a PIL transform has been performed.
void OptimizerStatsAnalysis::updateModuleStats(TransformationContext &Ctx) {
   assert(&getModule() == &Ctx.getModule());

   auto &ModStat = getModuleStat();
   auto OldModStat = ModStat;
   ModuleStat NewModStat;

   // First, collect statistics that require scanning PILFunctions.
   if (OldModStat.FunctionCount == 0) {
      // This is the first time the stats are computed for the module.
      // Iterate over all functions in the module and compute the stats.
      for (auto &F : M) {
         auto &FuncStat = getFunctionStat(&F);
         FunctionStat NewFuncStat(&F);
         processFuncStatHistory(&F, NewFuncStat, Ctx);
         // Update function stats.
         FuncStat = NewFuncStat;
         // Update module stats.
         NewModStat.addFunctionStat(NewFuncStat);
      }
   } else {
      // Go only over functions that were changed since the last computation.
      // These are the functions that got invalidated, removed or added.
      //
      // If no functions were changed by the last executed transformation, then
      // the sets of invalidated, deleted and added functions will be empty and
      // no FunctionStats will be updated.
      //
      // FIXME: As a result, the current implementation does not record the fact
      // about performing a given transformation on a given function, if the
      // function was not changed during the transformation. This reduced the
      // amount of recorded information, but makes the history of transformations
      // on a given function incomplete. If this ever becomes an issue, we can
      // record all transformations, even if they do not change anything.
      NewModStat = OldModStat;

      // Process modified functions.
      while (!InvalidatedFuncs.empty()) {
         auto *F = InvalidatedFuncs.back();
         InvalidatedFuncs.pop_back();
         auto &FuncStat = getFunctionStat(F);
         auto OldFuncStat = FuncStat;
         FunctionStat NewFuncStat(F);
         processFuncStatsChanges(F, OldFuncStat, NewFuncStat, Ctx);
         NewModStat.subFunctionStat(OldFuncStat);
         NewModStat.addFunctionStat(NewFuncStat);
         FuncStat = NewFuncStat;
      }

      // Process deleted functions.
      while (!DeletedFuncs.empty()) {
         auto *F = DeletedFuncs.back();
         DeletedFuncs.pop_back();
         auto &FuncStat = getFunctionStat(F);
         auto OldFuncStat = FuncStat;
         FunctionStat NewFuncStat;
         processFuncStatsChanges(F, OldFuncStat, NewFuncStat, Ctx);
         NewModStat.subFunctionStat(OldFuncStat);
         Cache->deleteFunctionStat(F);
      }

      // Process added functions.
      while (!AddedFuncs.empty()) {
         auto *F = AddedFuncs.back();
         AddedFuncs.pop_back();
         auto &FuncStat = getFunctionStat(F);
         FunctionStat OldFuncStat;
         FunctionStat NewFuncStat(F);
         processFuncStatsChanges(F, OldFuncStat, NewFuncStat, Ctx);
         NewModStat.addFunctionStat(NewFuncStat);
         FuncStat = NewFuncStat;
      }
   }

   // Then collect some more general statistics, which do not require
   // any scanning of PILFunctions or the like.
   NewModStat.addMemoryStat();
   NewModStat.addCreatedAndDeletedInstructionsStat();

   // Process updates.
   processModuleStatsChanges(OldModStat, NewModStat, Ctx);

   // Remember the new state of the collected stats.
   ModStat = NewModStat;
}

FunctionStat::FunctionStat(PILFunction *F) {
   InstCountVisitor V(InstCounts);
   V.visitPILFunction(F);
   BlockCount = V.getBlockCount();
   InstCount = V.getInstCount();
}

} // end anonymous namespace

/// Updates PILModule stats after finishing executing the
/// transform \p Transform.
///
/// \param M PILModule to be processed
/// \param Transform the PIL transformation that was just executed
/// \param PM the PassManager being used
void polar::updatePILModuleStatsAfterTransform(PILModule &M,
                                               PILTransform *Transform,
                                               PILPassManager &PM,
                                               int PassNumber, int Duration) {
   if (!PILStatsModules && !PILStatsFunctions && !PILStatsDumpAll)
      return;
   TransformationContext Ctx(M, PM, Transform, PassNumber, Duration);
   OptimizerStatsAnalysis *Stats = PM.getAnalysis<OptimizerStatsAnalysis>();
   Stats->updateModuleStats(Ctx);
}

// This is just a hook for possible extensions in the future.
// It could be used e.g. to detect sequences of consecutive executions
// of the same transform.
void polar::updatePILModuleStatsBeforeTransform(PILModule &M,
                                                PILTransform *Transform,
                                                PILPassManager &PM,
                                                int PassNumber) {
   if (!PILStatsModules && !PILStatsFunctions)
      return;
}

PILAnalysis *polar::createOptimizerStatsAnalysis(PILModule *M) {
   return new OptimizerStatsAnalysis(M);
}
